#include"DynamicArray.h"
#include<iostream>
#include<cmath>

DynamicArray::DynamicArray(size_t capacity) : size(0), capacity(capacity)//构造函数
{
    array = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray& a)//拷贝构造函数
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
}

DynamicArray &DynamicArray::operator=(const DynamicArray& a)//赋值运算符重载
{
    delete[] array;
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
    return *this;
}

DynamicArray::~DynamicArray()//析构函数
{
    delete[] array;
}

size_t DynamicArray::Size()
{
    return size;
}

void DynamicArray::ReSize(size_t capacity)//扩容
{
    this->capacity = capacity;
    this->size = (size>capacity)?capacity:size;

    ElementType* newP = new ElementType[capacity];
    for(size_t i = 0; i < size; i++)
    {
        newP[i] = array[i];
    }
    delete[] array; 
    array = newP;
}

void DynamicArray::InsertTail(const ElementType& element)//尾插
{
    if(size >= capacity)
        ReSize(capacity*2);
    array[size++] = element;//O(1);
}

void DynamicArray::InsertHead(const ElementType &element)//头插
{
    if(size >= capacity)
        ReSize(capacity*2);

    for(size_t i = size; i > 0; i--)//O(n)
    {
        array[i] = array[i-1];
    }
    array[0]=element;
    size++;
}

void DynamicArray::InsertByIndex(int index, const ElementType &element)//中间插入
{
    //非法位置排除
    if(index < 0 || index > size)
        return;
    //扩容
    if(size >= capacity)
        ReSize(capacity*2);

    for(size_t i = size; i > index; i--)//O(n)
    {
        array[i] = array[i-1];
    }
    array[index] = element;
    size++;
}

void DynamicArray::RemoveByIndex(int index)//按位置删除
{
    //非法位置排除
    if(index < 0 || index >= size)
        return;
    //删除
    for(size_t i = index; i < size-1; i++)//O(n)
    {
        array[i] = array[i+1];
    }
    size--;
}

void DynamicArray::RemoveByElement(const ElementType &element)//按值删除
{
    for(size_t i = 0; i < size; i++)//O(n^2)
    {
        if(array[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

ElementType* DynamicArray::FindByIndex(int index)//按位置查找
{
    if(index < 0 || index >= size)
        return nullptr;
    return &array[index];//O(1)
}  

DynamicArray DynamicArray::FindByElement(const ElementType &element)//按值查找
{
    DynamicArray result;
    for(int i = 0; i < size; i++)//O(n)
    {
        if(array[i] == element)
            result.InsertTail(new int(i));//把下标插入到新对象
    }
    return result;
}

ElementType DynamicArray::FindElement(DynamicArray* a,std::string elem1,int elem2,bool(*EqualPtr)(ElementType,std::string,int)) // 按值查找
{
    for(int i = 0; i < a->size; i++)//O(n)
    {
        if(EqualPtr(a->array[i],elem1,elem2)==true)
           return a->array[i];
    }
    return nullptr;
}

void DynamicArray::UpdateByIndex(int index, const ElementType &element)//按位置修改
{
    if(index < 0 || index >= size)
        return;
    array[index] = element;//O(1)
}

void DynamicArray::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)//按值修改
{
    for(int i = 0; i < size; i++)//O(n)
    {
        if(array[i] == oldValue)      
            array[i] = newValue;
    }
}

void DynamicArray::Sort(bool (*SortPtr)(ElementType, ElementType))//排序
{
    FastSort(0,size-1,0,2*log2(size),SortPtr);//O(nlogn) 
}

void DynamicArray::Duplicate(bool(*EqualPtr)(ElementType, ElementType))//去重算法
{
    for(int i=1;i<size;i++)
    {
        if(EqualPtr(array[i],array[i-1])==true)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

DynamicArray DynamicArray::Merge(const DynamicArray &a,bool(*EqualPtr)(ElementType, ElementType))//归并
{
    size_t first=0;//当前数组
    size_t second=0;//传进来的数组
    DynamicArray result;
    //遍历两个数组都没到结尾
    while(first<this->size&&second<a.size)
    {
        if(EqualPtr(a.array[second],this->array[first])==true)
        {
            result.InsertTail(array[first++]);
        }
        else
        {
            result.InsertTail(a.array[second++]);
        }
    }
    while(first<this->size)
    {
        result.InsertTail(array[first++]);
    }
    while(second<a.size)
    {
        result.InsertTail(a.array[second++]);
    }
    return result;
}

DynamicArray DynamicArray::FindInterSection(const DynamicArray &a,bool(*EqualPtr)(ElementType, ElementType),bool(*SortPtr)(ElementType, ElementType))//找交集
{
    DynamicArray result;
    int first=0;
    int second=0;
    while(first<size&&second<a.size)//O(n)
    {
        if(EqualPtr(array[first],a.array[second])==true)
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(SortPtr(array[first],a.array[second])==true)
        {
            second++;
        }
        else
        {
            first++;
        }
    }
    return result;
}

DynamicArray DynamicArray::FindUnionSection(const DynamicArray &a,bool(*EqualPtr)(ElementType, ElementType),bool(*SortPtr)(ElementType, ElementType))//找并集
{
    DynamicArray result;
    int first=0;
    int second=0;
    while(first<size&&second<a.size)//O(n)
    {
        if(EqualPtr(array[first],a.array[second])==true)
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(SortPtr(array[first],a.array[second])==true)
        {
            result.InsertTail(a.array[second++]);
        }
        else
        {
            result.InsertTail(array[first++]);
        }
    }
    while(first<this->size)
    {
        result.InsertTail(array[first++]);
    }
    while(second<a.size)
    {
        result.InsertTail(a.array[second++]);
    }
    return result;

}

DynamicArray DynamicArray::FindDifferentSection(const DynamicArray &a,bool(*EqualPtr)(ElementType, ElementType),bool(*SortPtr)(ElementType, ElementType))//找补集
{
    DynamicArray result;
    int first=0;
    int second=0;
    while(first<size&&second<a.size)//O(n)
    {
        if(EqualPtr(array[first],a.array[second])==true)
        {
            first++;
            second++;
        }
        else if(SortPtr(array[first],a.array[second])==true)
        {
            result.InsertTail(a.array[second++]);
        }
        else
        {
            result.InsertTail(array[first++]);
        }
    }
    while(first<this->size)
    {
        result.InsertTail(array[first++]);
    }
    while(second<a.size)
    {
        result.InsertTail(a.array[second++]);
    }
    return result;
}

bool DynamicArray::operator==(const DynamicArray& a)//判断两个数列是否相等
{
    if(size!=a.size)
        return false;
    int first=0;
    int second=0;
    while(first<size&&second<a.size)
    {
        if(array[first++]!=a.array[second++])
            return false;      
    }
    return true;
}

size_t DynamicArray::BinarySearch(const ElementType& element)//二分法
{
    int left=0;
    int right=size-1;
    while(left<=right)
    {
        size_t mid=left+(right-left)/2;
        if(array[mid]==element)
            return mid;
        else if(array[mid]>element)
        {
            if(mid==0)
                return ULONG_MAX;
            right=mid-1;
        }
        else
            left=mid+1;
    }
    return ULONG_MAX;
}

bool DynamicArray::IsChild(const DynamicArray &a,bool(*EqualPtr)(ElementType, ElementType))//查找一个数列是不是子数列
{
    // for(int i=0;i<a.size;i++)//O(n)
    // {
    //     //没找到
    //     if(FindByElement(a.array[i]).size==0)
    //         return false;
    // }
    // return true;

    int j=0;
    for(int i=0;i<size;i++)//O(n)
    {
        if(EqualPtr(array[i],a.array[j])==true)
        {
            j++;
        }
    }
    return j==a.size;
}

//滑动窗口算法
bool DynamicArray::IsContinueChild(const DynamicArray &a,bool(*EqualPtr)(ElementType, ElementType))//查找连续子数列
{
    for(int i=0;i<=size-a.size;i++)//O(n^2)
    {
        if(subsequence(i,a.size)==a)
        {
            return true;
        }
    }
    return false;
}

DynamicArray DynamicArray::subsequence(int index, size_t size)//获取子序列
{
    if(index<0||index+size>this->size)
        return DynamicArray();
    DynamicArray result;
    for(int i=index;i<index+size;i++)
    {
        result.InsertTail(array[i]);
    }
    return result;
}

void DynamicArray::show(void(*PrintPtr)(ElementType))//显示
{
    for(int i = 0; i < size; i++)
    {
        PrintPtr(array[i]);
    }
    std::cout << std::endl;
}

void DynamicArray::SetFreePtr()
{
    if(array!=nullptr)
    {
        delete[] array;
        array=nullptr;
    }
}

void DynamicArray::FastSort(size_t start, size_t end,size_t deepth,size_t MaxDepth,bool (*SortPtr)(ElementType, ElementType))//快速排序
{
    if(start >= end)
        return;
    //如果超过最大深度
    if(deepth>MaxDepth)
    {
        //改用插入排序
        InsertSort(start,end,SortPtr);
    }
    //如果没有超过最大深度，继续快排分组
    else
    {
        size_t par=Partition(start,end,SortPtr);
        if(par!=0)
            FastSort(start, par-1,deepth+1,MaxDepth,SortPtr);
        FastSort(par+1, end,deepth+1,MaxDepth,SortPtr);
    }

}

void DynamicArray::InsertSort(size_t start, size_t end,bool (*SortPtr)(ElementType, ElementType))//插入排序
{
    for(size_t i=start;i<end;i++)
    {
        size_t j=i;
        ElementType temp=array[i];
        for(;j>start;j--)
        {
            if(SortPtr(array[j-1],temp)==true)
            {
                array[j]=array[j-1];
            }
            else
            {
                break;
            }
        }
        array[j]=temp;
    }
}

size_t DynamicArray::Partition(size_t start, size_t end,bool (*SortPtr)(ElementType, ElementType))//分组 
{
    size_t left = start;
    size_t right = end;
    ElementType temp = array[start];

    while(left < right)
    {
        while((SortPtr(array[right],temp)==true) && left < right )
            right--;
        if(left < right)
            array[left++] = array[right];
        while((SortPtr(temp,array[left])==true)  && left < right )
            left++;
        if(left < right)
            array[right--] = array[left];
    }
    array[left] = temp;
    return left;
}